1. Field of Invention
The present invention relates generally to the field of database management systems. More specifically, the present invention is related to a decimal identification system for ordered nodes.
2. Discussion of Prior Art
A tree structure comprising nodes is a type of data structure in which each element is attached to one or more elements directly beneath it. The connections among elements in a tree structure are called branches. Trees are often called inverted trees because they are normally drawn with the root at the top. Inverted trees are the data structures used to represent hierarchical file structures. In this case, the leaves are files and the other elements above the leaves are directories.
Tree structures have been used in prior art data processing systems to organize data. But, such prior art fails to provide for a node identification system for ordered nodes wherein adding or deleting a child node (or a subtree of nodes) from a hierarchical structure of nodes still maintains the order and relationships between the parent, child, and sibling nodes.
Node identification solutions based upon assigning pre-order traversal and/or postorder traversal numbers can only provide an ordering solution as such solutions cannot be used to identify sibling relationships between nodes.
FIG. 1 illustrates a node identification solution wherein a concatenation of values are assigned. The root node is assigned an ID of 0. The root node's first child is assigned an ID composed of the parent's ID (0) and a 0. The root node's second child is assigned an ID composed of the parent's ID (0) and a 1. This process is repeated until all nodes are assigned IDs. This system establishes a total ordering for the nodes, i.e., 0<0.0<0.0.0<0.0.1<0.0.2<0.0.2.0<0.0.2.1<0.1< . . . 0.2.2. In addition, the system identifies parent, child and sibling relationships. That is, 0.1 is the parent of 0.1.0 and 0.1.1 because 0.1 is the prefix in both children, and that 0.1.0 and 0.1.1 are siblings because they have the same prefix.
The problem with this system, shown in FIG. 1, is that changes to the hierarchy would require the re-numbering of IDs to maintain the order of the nodes. For example, as in FIG. 2a, adding a node B would require the re-numbering of the node with an ID of 0.2.2, and adding a node C would require the re-numbering of nodes with IDs 0.0.0, 0.0.1, and 0.0.2, including re-numbering any children of such nodes. Adding a node A, however, would not require re-numbering because the new node can be assigned an ID of 0.0.2.2.
FIG. 2b illustrates the modified hierarchical structure of nodes after the insertion of node A, B, and C. The filled nodes (0.0.1, 0.0.2, 0.0.3, 0.0.3.0, 0.0.3.1, and 0.2.3) represent nodes whose values have changed due to the insertion of nodes A, B, or C. The double circle nodes (0.0.0, 0.0.3.2, and 0.2.2) represent nodes that are newly inserted. Hence, it can be seen that the insertion of a new node (or, similarly, the deletion of an existing node) causes a change in the ID values associated with other nodes in a hierarchical structure of nodes.
The following references provide a general teaching in ordering nodes, but they fail to provide for a solution wherein existing ID values can remain the same even after changes (such as insertion or deletion of nodes) are made in a hierarchical structure of nodes.
The patent to Jordan, Jr. (U.S. Pat. No. 5,063,502) provides for an apparatus and method for controlling concurrent process access of infrastructures comprising tree structures of complex object nodes. The apparatus associated with each complex object node records an accumulate count of each type of lock applied by concurrently running computer processes against each infrastructure complex node.
The patent to Kothuri et al. (U.S. Pat. No. 6,505,205) provides for a system and method for indexing and storing multi-dimensional or multi-attribute data. Data items are recursively sorted in a selected dimension (e.g., the dimension having the greatest variance) and divided until each sub-division fits into a leaf node having a specified fanout. Intermediate nodes and a root node are constructed to complete the index. Each node of the index is stored in a database as a separate object or record and may include a node identifier of the unique, an identifier of a parent and/or a sibling node and an entry for each child of the node, which may be data items or other nodes. Each record entry for a child includes an associated bounding area encompassing descendant data items. Another database table or module may store information about the index, such as the dimensionality of the data, the index fanout and an identifier of a root of the index.
The patent application publication to Keating (2002/0052895) discloses a system and method for generalizing the content in a formatted document, wherein the system and method permit a group with multiple elements to be processed rapidly even if the number of elements in the group changes over time.
Whatever the precise merits, features, and advantages of the above cited references, none of them achieves or fulfills the purposes of the present invention.